A. Technical Field
This application relates to a method of transferring data over one or more networks and, more specifically, to a method of minimizing the storage associated with routing tables in network devices connecting one or more networks.
B. Background of the Invention
The growth of the Internet, and the World Wide Web (Web) in particular, has led to enormous increases in the amount of traffic flowing over the group of connected networks that comprise the Internet and connected network systems. Access providers such as Internet Service Providers (ISPs) provide connections for businesses and individuals to connect to the Internet and access the Web. ISPs and other networks, such as intranets and extranets, must interconnect in order to allow their customers to reach points on the Internet serviced by other ISPs and/or other networks.
The Internet is currently implemented using the TCP and IP protocols, which allow information to be routed within the Internet. The Internet is, thus, an example of an IP network. Other examples of IP networks exist. In the future, the Internet may continue to use the TCP/IP protocols or may use some variation of the TCP/IP protocols.
In general, an IP network, such as the Internet, is composed of a number of IP networks. For example, an ISP may be a sub-network. Similarly, a network that connects ISPs may be an IP sub-network. An Intranet may be another example of an IP sub-network.
There are two types of IP sub-networks: edge sub-networks and transit networks. A transit sub-network is an IP sub-network that is not the destination for a specific IP flow. An edge IP sub-network is an IP sub-network that is a destination for a specific IP flow. An IP flow is a collection of IP packets, or groups of data, that all contain the same source and destination address. An IP flow may also be defined to a finer granularity to include, for example, the application and type of service in addition to the source and destination address. A particular IP sub-network can be both a transit sub-network and an edge sub-network for different IP flows. An edge IP sub-network is generally connected to another IP sub-network using an IP router, which is a device or, in some cases, software in a general purpose computer, that determines the next network point to which a data packet should be forwarded toward its destination.
Some IP networks route packets using a protocol know as BGP (Border Gateway Protocol). In the BGP protocol, each IP router contains a routing table that contains the “next hop” to a connection that a packet should take from the current router to reach its final destination.
In current implementations of the BGP routing method, routing tables include entries for a large number of destinations. The routing table in a router is updated with new and changed routing information using the BGP routing method. Because routing tables contain routes for a large number of destinations, the tables can become quite voluminous. As a network (such as the Internet) grows, the size of the routing tables becomes problematic. This problem is greater at customer locations using inexpensive routing equipment with a small amount of routing table storage.
What is needed is a system and method that reduces the amount of memory required by the routing tables in a router.